1. Field of the Invention
The present invention relates generally to an encrypting system using an Error Correction Code (ECC) and, in particular, to an encryption method and apparatus providing increased protection for data from an external attack by puncturing or repeating a part of coded data.
2. Description of the Related Art
Typically, an ECC is used to correct errors occurring between a transmitter and a receiver in a communication system. In the error correction process, a given data m with a length of K, which is to be encrypted, is input to an error correction encoder, which generates a parity p with a length of (N−K) for a codeword c=(m, p) with the length N, matching 1:1 with each other, to be transmitted to the receiver. The receiver generates an error vector e with the length of N and receives (c+e). In the decoding process with the error correction code at the receiver, the error vector e is removed to recover the codeword c and, as a consequence, it is also possible to recover the data m.
Here, the codeword c is distorted by the error vector e and thus it is difficult for a system having no error correction capability to recover the data m. With this principle, the ECC can be adopted to an encrypting system.
However, the conventional encrypting system based on the ECC has a drawback in that data may be obtained by unauthorized persons through the repetitive observation and is thus vulnerable to an external attack.
More specifically, when data m is input to an error correction encoder, which outputs codeword c and is then encrypted with a random error vector e in order to be output as encrypted data (c+e), if the feature of the encoder is not known, it is impossible to perform decoding and thus to correct an error, resulting in no encrypted data. However, when the error vector e includes the errors out of the error correction capability of the ECC, decoding is likely to fail even with the knowledge about features of the encoder, such that the error occurrence range of the error vector e has to be in the range of the error correction capability of the ECC.
FIG. 1 is block diagram illustrating a coding procedure of a conventional ECC-based encryption system. Typically, an ECC-based encrypting system as illustrated in FIG. 1 improves an encrypting level.
Referring to FIG. 1, data m is input to an inverse conversion-enabled converter 110. For example, the inverse conversion-enabled conversion may be exemplified by an encrypting process in which a matrix having its inverse matrix is multiplied.
The conversion result is input to an ECC encoder 120 to generate the codeword c, which is input to an interleaver 130 to generate the interleaved result s. Here, the random error vector e generated by the error generator 140 is added to the interleaved result s in order to generate the signal v=(s+e) as final encrypted data. The total number of errors in the error vector e does not exceed the error correction capability of the error correction code.
FIG. 2 is a block diagram illustrating a decoding procedure of a conventional encrypting system with an ECC.
Referring to FIG. 2, in order to decrypt the encrypted data, the receiver performs de-interleaving through a de-interleaver 210, which rearranges the encrypted data, and performs decoding with an ECC through the ECC decoder 220. Finally, the inverse converter 230 acquires an estimated value m′ of the original data m. If the number of errors is in the correction capability range of the ECC, m′=m is obvious.
In order for an unauthorized user to recover the data m, the unauthorized user must estimate the information on the converter 110, encoder 120, and interleaver 130. Accordingly, the data is encrypted with 3-stage encrypting level.
Because distortion deteriorates as the number of errors included in the error vector e increases, such an encrypting system shows a good encrypting effect. However, in order to remove such errors, superior ECCs are used. Because the conventional systematic code defined in the form of c=(m, p) in which the parity p is generated for the data m is known to be superior in performance, the system for encrypting data with error correction code is designed based on the systematic code in general. Also, the performance of the systematic code-based encrypting system is improved in proportion to the amount of p. As the amount of p increases, the code-rate of the error correction code decreases, resulting in reduction of data transfer efficiency.
However, the above-described encrypting system has a significant shortcoming as will be described below.
When an unauthorized user continues observing the same data, the unauthorized user may observe the encrypted data corresponding to the data m as follows:
            First      ⁢                          ⁢      observation      ⁢              :            ⁢                          ⁢                        v          _                1              =          (                        s          _                +                              e            _                    1                    )                  Second      ⁢                          ⁢      observation      ⁢              :            ⁢                          ⁢                        v          _                1              =          (                        s          _                +                              e            _                    2                    )        …                    D        th            ⁢      observation      ⁢              :            ⁢                          ⁢                        v          _                D              =          (                        s          _                +                              e            _                    D                    )      
If the user sums up all of the observation results, it can be expressed as shown in Equation (1).
                                                                        v                _                            1                        +                                          v                _                            2                        +            …            +                                          v                _                            D                                D                =                                            s              _                        +                                                                                e                    _                                    1                                +                                                      e                    _                                    2                                +                …                +                                                      e                    _                                    D                                            D                                |                                    (        1        )            
Typically, the error rate in the error vector is less than 50%, because, if the error rate reaches 50%, it is impossible to recover the data with any ECC. When the error rate is less than 50%, the value of
                    e        _            1        +                  e        _            2        +    …    +                  e        _            D        Dshows a certain tendency.
For example, assuming that the error vectors are binary vectors composed of 0 and 1, and include an error rate less than 50%, for convenience purposes,
                    e        _            1        +                  e        _            2        +    …    +                  e        _            D        Dis characterized in that each of its elements is less than ½. Theoretically, assuming that the error rate of the error vector is X (<½ and the number of observations is infinite, i.e., the value D is infinite), X can be expressed as shown in Equation (2).
                                          lim                          D              →              ∞                                ⁢                                                                      e                  _                                1                            +                                                e                  _                                2                            +              …              +                                                e                  _                                D                                      D                          =                              (                          X              ,              X              ,              …              ⁢                                                          ,              X                        )                    |                                    (        2        )            
Accordingly, the observer can remove the encrypting effect derived by the error vector with a process of Equation (3) through a large number of observations.
                                          s            ′                    _                =                                                                              v                  _                                1                            +                                                v                  _                                2                            +              …              +                                                v                  _                                D                                      D                    -                      (                          X              ,              X              ,              …              ⁢                                                          ,              X                        )                                              (        3        )            
Due to this shortcoming of the ECC-based encrypting system, if s of FIG. 1 is detected easily and if the converter 110 and interleaver 130 are exposed to other users, the data m is likely to be exposed with the systematic ECC. That is, although the encrypting system uses 3 stages, the role of the ECC may become useless, resulting in basically a two-stage encrypting level.